package graph;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class WeightedGraph {

    private final int MAX_SIZE = 10;
    
    private List<Vertex> vertexList = null;
    private int[][] adjMat = null;
    private int nVerts = 0;
    
    public WeightedGraph() {
        vertexList = new LinkedList<Vertex>();
        adjMat = new int[MAX_SIZE][MAX_SIZE];
        
        for (int row = 0; row < MAX_SIZE; row++) {
            for (int col = 0; col < MAX_SIZE; col++) {
                adjMat[row][col] = 0;
            }
        }
    }
    
    public void addVertex(char label) {
        if (nVerts > MAX_SIZE) {
            return;
        }
        Vertex vertex = new Vertex(label);
        vertexList.add(vertex);
        nVerts++;
    }
    
    public void addEdge(int start, int end, int weighted) {
        adjMat[start][end] = weighted;
        adjMat[end][start] = weighted;
    }
    
    public void mst() {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(0);
        vertexList.get(0).setWasVisited(true);
        while (!queue.isEmpty()) {
            int current = queue.peek();
            int location = getLeastWeighted(queue);
            if (location == -1) {
                queue.poll();
            } else {
                queue.add(new Integer(location));
                queue.add(new Integer(current));
                this.displayVertex(vertexList.get(current));
                this.displayVertex(vertexList.get(location));
                System.out.print(" ");
                vertexList.get(location).setWasVisited(true);
            }
        }
    }
    
    public int getLeastWeighted(Queue<Integer> queue) {
        int weighted = Integer.MAX_VALUE;
        int location = -1;
        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (int i = 0; i < nVerts; i++) {
                if (vertexList.get(i).getWasVisited() == false
                        && adjMat[v][i] > 0) {
                    if (weighted > adjMat[v][i]) {
                        weighted = adjMat[v][i];
                        location = i;
                    }
                }
            }
        }
        return location;
    }
    
    public void displayVertex(Vertex vertex) {
        System.out.print(vertex.getLabel());
    }
}
